package source.stack;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class Stack1 {
    /**
     * 有效的括号
     * <p>
     * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ,判断字符串是否有效。
     * 有效字符串需满足：
     * 左括号必须用相同类型的右括号闭合。
     * 左括号必须以正确的顺序闭合。
     * 每个右括号都有一个对应的相同类型的左括号。
     *
     * @param s s = "()"
     * @return true
     */
    public boolean isValid(String s) {
        List<Character> list = new ArrayList<>();
        char[] cs = s.toCharArray();
        for (char c : cs) {
            if (c == '(' || c == '{' || c == '[')
                list.add(c);
            else {
                if (list.isEmpty())
                    return false;
                char lastOne = list.get(list.size() - 1);
                if (lastOne == '(' && c == ')' || lastOne == '{' && c == '}' || lastOne == '[' && c == ']')
                    list.remove(list.size() - 1);
                else
                    return false;
            }
        }
        return list.isEmpty();
    }

    public String simplifyPath(String path) {
        String[] dirs = path.split("/+");
        List<String> list = new ArrayList<>();
        for (String dir : dirs) {
            if (dir.isEmpty() || dir.equals(".") || dir.equals("..") && list.isEmpty()) {
                continue;
            }
            if (dir.equals("..") && !list.isEmpty()) {
                list.remove(list.size() - 1);
            } else {
                list.add("/" + dir);
            }
        }
        StringBuilder res = new StringBuilder();
        for (String s : list) {
            res.append(s);
        }

        return res.isEmpty() ? "/" : res.toString();
    }

    /**
     * 逆波兰表达式求值
     * <p>
     * 给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。
     * 请你计算该表达式。返回一个表示表达式值的整数。
     * 注意：
     * 有效的算符为 '+'、'-'、'*' 和 '/' 。
     * 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
     * 两个整数之间的除法总是 向零截断 。
     * 表达式中不含除零运算。
     * 输入是一个根据逆波兰表示法表示的算术表达式。
     * 答案及所有中间计算结果可以用 32 位 整数表示。
     *
     * @param tokens 后缀表达式
     * @return 计算结果
     */
    public int evalRPN(String[] tokens) {
        Stack2 stack2 = new Stack2();
        for (String s : tokens) {
            switch (s) {
                case "+":
                    stack2.push(stack2.pop() + stack2.pop());
                    break;
                case "*":
                    stack2.push(stack2.pop() * stack2.pop());
                    break;
                case "/":
                    int a = stack2.pop();
                    int b = stack2.pop();
                    stack2.push(b / a);
                    break;
                case "-":
                    a = stack2.pop();
                    b = stack2.pop();
                    stack2.push(b - a);
                    break;
                default:
                    stack2.push(Integer.parseInt(s));
            }
        }

        return stack2.pop();
    }


    /**
     * 给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
     * 注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。
     * <p>
     * s 由数字、'+'、'-'、'('、')'、和 ' ' 组成
     * s 表示一个有效的表达式
     * '+' 不能用作一元运算(例如， "+1" 和 "+(2 + 3)" 无效)
     * '-' 可以用作一元运算(即 "-1" 和 "-(2 + 3)" 是有效的)
     * 输入中不存在两个连续的操作符
     * 每个数字和运行的计算将适合于一个有符号的 32位 整数
     *
     * @param s 中缀表达式
     * @return 结果
     */
    public int calculate(String s) {
        int result = 0;
        Deque<Integer> stack = new LinkedList<>();
        stack.push(1);
        int sign = 1;
        int i = 0;
        while (i < s.length()) {
            if (s.charAt(i) == ' ') ;
            else if (s.charAt(i) == '+')
                sign = stack.peek();
            else if (s.charAt(i) == '-')
                sign = -stack.peek();
            else if (s.charAt(i) == '(')
                stack.push(sign);
            else if (s.charAt(i) == ')')
                stack.pop();
            else {
                int num = 0;
                while (i < s.length() && Character.isDigit(s.charAt(i))) {
                    num = num * 10 + s.charAt(i) - '0';
                    i++;
                }
                result += num;
                continue;
            }
            i++;
        }
        return result;
    }




}


class Stack2 {
    private final List<Integer> list = new ArrayList<>();

    public Integer pop() {
        return list.remove(list.size() - 1);
    }

    public void push(Integer i) {
        list.add(i);
    }
}
